/*
 * @lc app=leetcode.cn id=111 lang=cpp
 *
 * [111] 二叉树的最小深度
 *
 * https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/description/
 *
 * algorithms
 * Easy (49.99%)
 * Likes:    714
 * Dislikes: 0
 * Total Accepted:    364.7K
 * Total Submissions: 729.3K
 * Testcase Example:  '[3,9,20,null,null,15,7]'
 *
 * 给定一个二叉树，找出其最小深度。
 * 
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 * 
 * 说明：叶子节点是指没有子节点的节点。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：2
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：root = [2,null,3,null,4,null,5,null,6]
 * 输出：5
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 树中节点数的范围在 [0, 10^5] 内
 * -1000 
 * 
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // int minDepth(TreeNode* root) {
    //     //层序遍历--广度优先遍历
    //     queue<TreeNode*> que;
    //     TreeNode* cur = root;
    //     if(cur == NULL) return 0;
    //     que.push(cur);
    //     int depth = 0;

    //     while(!que.empty()){
    //         int size = que.size();
    //         depth++;
    //         for(int i = 0;  i < size; i++){
    //             cur = que.front();
    //             que.pop();
    //             if (cur->left == NULL && cur->right == NULL) return depth;
    //             if (cur->left) que.push(cur->left);
    //             if (cur->right) que.push(cur->right);
    //         }
    //     }
    //     return depth;
    // }



    // //后序遍历-左右中-深度优先遍历
    // int minDepth(TreeNode* root) {
    //     if(root == NULL) return 0;
    //     int res = getDepth(root);
    //     return res;
    // }

    // int getDepth(TreeNode* node){
    //     if(node == NULL) return 0;
    //     int leftDepth = getDepth(node->left);
    //     int rightDepth = getDepth(node->right);

    //     //以下注释的代码是相比于二叉树的最大深度的区别所在
    //     //最小深度 意味着 该节点的左右孩子都是空，
    //     //而当，一边是空，另一边是非空 的时候
    //     //就意味着，要取 非空的一边 为确定的深度，空的一边的深度并不可取，并不是最小的，另一边还存在深度
    //     //而不是说，像求取最大深度那样，直接取最大的（有孩子的那一边）

    //     //当一个左子树为空，而右子树不为空，这时并不是最低点
    //     //有孩子的那一边才是最低点
    //     if(node->left == NULL && node->right != NULL) {
    //         return 1 + rightDepth;
    //     }

    //     //当一个左子树不为空，而右子树为空，这时并不是最低点
    //     //有孩子的那一边才是最低点
    //     if(node->left != NULL && node->right == NULL) {
    //         return 1 + leftDepth;
    //     }

    //     //这种情况是左右子树都不为空
    //     //左右孩子是空的情况早已经退出去了
    //     int res = 1 + min(leftDepth, rightDepth);
    //     return res;
    // }

    //后序遍历-左右中-深度优先遍历
    int minDepth(TreeNode* root) {
        if(root == NULL) return 0;
        int leftDepth = minDepth(root->left);
        int rightDepth = minDepth(root->right);

        if(root->left == NULL && root->right != NULL) {
            return 1 + rightDepth;
        }
        if(root->left != NULL && root->right == NULL) {
            return 1 + leftDepth;
        }  
              
        int res = 1 + min(leftDepth, rightDepth);
        return res;
    }

};
// @lc code=end

